"""
567. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
"""
from collections import Counter


class Solution:

    def checkInclusion(self, s1: str, s2: str) -> bool:
        left = 0
        right = 0
        need = Counter(s1)
        window = Counter()
        valid = 0

        while right < len(s2):
            # 扩大窗口
            c = s2[right]
            right += 1
            if c in need:
                window[c] += 1
                if need[c] == window[c]:
                    valid += 1

            while right - left >= len(s1):
                # 更新结果
                if valid == len(need):
                    return True
                # 减小窗口
                c = s2[left]
                left += 1
                if c in need:
                    if need[c] == window[c]:
                        valid -= 1
                    window[c] -= 1

        return False